package 题目集.hash.字符串哈希;

import java.util.Scanner;

/**
 * 问题：
 *  给你一个长度为n的字符串，有m个询问
 *  每个询问包含四个整数 l1,r1,l2,r2
 * ，请你判断 [l1,r1]
 *  和 [l2,r2]
 *  这两个区间所包含的字符串子串是否完全相同。
 *  字符串中只包含大小写英文字母和数字。
 */
//字符串哈希还可以代替KMP算法进行字符串匹配
//https://www.acwing.com/problem/content/843/
public class 生成子串哈希 {
    /**
     * 暴力解法：
     *  每次询问都遍历两个区间，判断是否相同，时间复杂度O(m*q)  q为询问的区间长度，m为次数
     * 优化：预处理哈希
     *     对母字符串中的每个前缀计算哈希值。如母字符串abcb：分别计算a,ab,abc,abcb的哈希值
     *     当需要计算l,r区间的哈希值时，只需要对0~r的哈希值减去0~l-1的哈希值乘以P的幂次即可.
     *     时间复杂度O(n+m)
     */
    static int n, m;
    static char[] str;
    static long[] hash;
    static long[] base; //存储P的幂次
    static long P = 131;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        sc.nextLine();
        str = sc.nextLine().toCharArray();
        hash = new long[n + 1];
        base = new long[n + 1];
        getHash();
        while (m-- > 0) {
            int l1 = sc.nextInt();
            int r1 = sc.nextInt();
            int l2 = sc.nextInt();
            int r2 = sc.nextInt();
            if (get(l1, r1) == get(l2, r2)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

    public static void getHash() {
        base[0] = 1;
        for (int i = 1; i <= n; i++) {
            base[i] = base[i - 1] * P;  //计算P的幂次
        }
        for (int i = 1; i <= n; i++) {
            hash[i] = hash[i - 1] * base[1] + str[i - 1];   //进一位再加上当前字符
        }
    }

    public static long get(int l, int r) {
        //hash[l-1]这里-1是因为包括l
        return hash[r] - hash[l - 1] * base[r - l + 1];
    }
}
